package com.Oct_TwentyTwo;

import java.util.Arrays;

/**
 * 1235. 规划兼职工作
 * 你打算利用空闲时间来做兼职工作赚些零花钱。
 *
 * 这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
 *
 * 给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
 *
 * 注意，时间上出现重叠的 2 份工作不能同时进行。
 *
 * 如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-profit-in-job-scheduling
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/22 19:49
 */

public class Solution1235 {

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n=startTime.length;
        int[] dp=new int[n+1];
        int[][] jobs=new int[n][];
        for (int i=0;i<n;i++)
        {
            jobs[i]=new int[]{startTime[i],endTime[i],profit[i]};
        }
        Arrays.sort(jobs,(a,b)-> {
            return a[1] - b[1];
        });
        System.out.println(Arrays.deepToString(jobs));
        for (int i=0;i<n;i++)
        {
            int j=binarySearch(jobs,i,jobs[i][0]);
            dp[i+1]=Math.max(dp[i],dp[j+1]+jobs[i][2]);
        }
        return dp[n];
    }

    int binarySearch(int[][] jobs,int right,int upper){
        int left=-1;
        while (left+1<right)
        {
            int mid=(left+right)/2;
            if (jobs[mid][1]<=upper) left=mid;
            else right=mid;
        }
        return left;
    }

    public static void main(String[] args) {
        Solution1235 solution1235=new Solution1235();
        System.out.println(solution1235.jobScheduling(new int[]{1,2,3,3},new int[]{3,4,5,6},new int[]{50,10,40,70}));
    }
}
